Proceedings of the 19th ACM Conference on Information and Knowledge Management

A Phrase%2DBased Method for Hierarchical Clustering of Web Snippets.


Learning from Concept Drifting Data Streams with Unlabeled Data.


A New Automatic Categorization Algorithm for Web Services.

A Double%2DWindow%2DBased Classification Algorithm for Concept Drifting Data Streams.

Pattern Matching with Flexible Wildcards and Recurring Characters.

Online Streaming Feature Selection.
We study an interesting and challenging problem, online streaming feature selection, in which the size of the feature set is unknown, and not all features are available for learning while leaving the number of observations constant. In this problem, the candidate features arrive one at a time, and the learner&#039;s task is to select a “best so far ” set of features from streaming features. Standard feature selection methods cannot perform well in this scenario. Thus, we present a novel framework based on feature relevance. Under this framework, a promising alternative method, Online Streaming Feature Selection (OSFS), is presented to online select strongly relevant and non-redundant features. In addition to OSFS, a faster Fast-OSFS algorithm is proposed to further improve the selection efficiency. Experimental results show that our algorithms achieve more compactness and better accuracy than existing streaming feature selection algorithms on various datasets. 1.
Mining distribution change in stock order streams.

Online Streaming Feature Selection.
We study an interesting and challenging problem, online streaming feature selection, in which the size of the feature set is unknown, and not all features are available for learning while leaving the number of observations constant. In this problem, the candidate features arrive one at a time, and the learner&#039;s task is to select a “best so far ” set of features from streaming features. Standard feature selection methods cannot perform well in this scenario. Thus, we present a novel framework based on feature relevance. Under this framework, a promising alternative method, Online Streaming Feature Selection (OSFS), is presented to online select strongly relevant and non-redundant features. In addition to OSFS, a faster Fast-OSFS algorithm is proposed to further improve the selection efficiency. Experimental results show that our algorithms achieve more compactness and better accuracy than existing streaming feature selection algorithms on various datasets. 1.
Sequential Pattern Mining with Wildcards.

A Nettree for Approximate Maximal Pattern Matching with Gaps and One%2DOff Constraint.

Ensemble pruning via individual contribution ordering.
An ensemble is a set of learned models that make decisions collectively. Although an ensemble is usually more accurate than a single learner, existing ensemble methods often tend to construct unnecessarily large ensembles, which increases the memory consumption and computational cost. Ensemble pruning tackles this problem by selecting a subset of ensemble members to form subensembles that are subject to less resource consumption and response time with accuracy that is similar to or better than the original ensemble. In this paper, we analyze the accuracy/diversity trade-off and prove that classifiers that are more accurate and make more predictions in the minority group are more important for subensemble construction. Based on the gained insights, a heuristic metric that considers both accuracy and diversity is proposed to explicitly evaluate each individual classifier’s contribution to the whole ensemble. By incorporating ensemble members in decreasing order of their contributions, subensembles are formed such that users can select the top p percent of ensemble members, depending on their resource availability and tolerable waiting time, for predictions. Experimental results on 26 UCI data sets show that subensembles formed by the proposed EPIC (Ensemble Pruning via Individual Contribution ordering) algorithm outperform the original ensemble and a state-ofthe-art ensemble pruning method, Orientation Ordering (OO) [16].
A matrix modular SVM robust to imbalanced data for efficient visual concept detection.

Rule Synthesizing from Multiple Related Databases.

Fast Orthogonal Nonnegative Matrix Tri%2DFactorization for Simultaneous Clustering.

OASNET an optimal allocation approach to influence maximization in modular social networks.

Adaptive Informative Sampling for Active Learning.
Many approaches to active learning involve periodically training one classifier and choosing data points with the lowest confidence, but designing a confidence measure is nontrivial. An alternative approach is to periodically choose data instances that maximize disagreement among the label predictions across an ensemble of classifiers. Many classifiers with different underlying structures could fit this framework, but some ensembles are more suitable for some data sets than others. The question then arises as to how to find the most suitable ensemble for a given data set. In this work we introduce a method that begins with a heterogeneous ensemble composed of multiple instances of different classifier types, which we call adaptive informative sampling. The algorithm periodically adds data points to the training set, adapts the ratio of classifier types in the heterogeneous ensemble in favor of the better classifier type, and optimizes the classifiers in the ensemble using stochastic methods. Experimental results show that the proposed method performs consistently better than homogeneous ensembles. Comparison with random sampling and uncertainty sampling shows that the algorithm effectively draws informative data points for training. 1
Discretization Methods.
Many machine learning and neurally inspired algorithms are limited, at least in their pure form, to working with nominal data. However, for many real-world problems, some provision must be made to support processing of continuously valued data. This paper presents empirical results obtained by using six different discretization methods as preprocessors to three different supervised learners on several real-world problems. No discretization technique clearly outperforms the others. Also, discretization as a preprocessing step is in many cases found to be inferior to direct handling of continuously valued data. These results suggest that machine learning algorithms should be designed to directly handle continuously valued data rather than relying on preprocessing or ad hoc techniques. 1.
A Random Decision Tree Ensemble for Mining Concept Drifts from Noisy Data Streams.

Exploratory analysis of protein translation regulatory networks using hierarchical random graphs.

Manifold Elastic Net A Unified Framework for Sparse Dimension Reduction

NESVM a Fast Gradient Method for Support Vector Machines

News Filtering and Summarization on the Web.

Integrating induction and deduction for noisy data mining.

Special issue on selected papers from IEEE DMF 2008.

A Modified Semi%2DSupervised Learning Algorithm on Laplacian Eigenmaps.

Nonnegative Matrix Factorization on Orthogonal Subspace.

ICDM 2009
Abstract—With the assistance of a domain expert, active learning can often select or construct fewer examples to request their labels to build an accurate classifier. However, previous works of active learning can only generate and ask specific queries. In real-world applications, the domain experts (or oracles) are often more readily to answer “generalized queries ” with don’t-care attributes. The power of such generalized queries is that one generalized query is often equivalent to many specific ones. However, overly general queries are not good as answers from the domain experts (or oracles) can be highly uncertain, and this makes learning difficult. In this paper, we propose a novel active learning algorithm that asks good generalized queries. We then extend our algorithm to construct new, hierarchical features for both nominal and numeric attributes. We demonstrate experimentally that, our new method asks significantly fewer queries compared with the previous works of active learning, even when the initial labeled dataset is very small, and the oracle is inaccurate in class probability estimations. Our method can be readily deployed in real-world data mining tasks where obtaining labeled examples is costly. This is an extension of the paper published in IEEE ICDM 2009 [16]. Keywords—active learning, domain expert, generalized query. 1
ICDM Workshops 2009

Hybrid Artificial Intelligence Systems
The Joint Warfare System (JWARS) is being equipped with a Commander Model (CM) to perform situation assessment and Course of Action (COA) selection, and a Commander Behavior Model (CBM) to bias decisions with a commander&#039;s leadership style. The CM is a hybrid artificial intelligence system that models doctrine through the use of fuzzy rule sets, together with a tree-based lookahead algorithm for the strategy. The CBM employs behaviorbased fuzzy rule sets to augment the CM in assessing the situation, and in biasing the COA selection criteria. Extending from Myers-Briggs personality traits, the CBM links personality traits to military attitudes, consequences and values. Employing the fuzzy rule sets, the resulting sets of values are combined to select a specific COA with an auditable trail. Users will have the ability to modify both the input parameters and the underlying rules. The CM/CBM is applicable to decisions at multiple echelons.
Mining Frequent Patterns with Gaps and One%2DOff Condition.

A relation extraction method of Chinese named entities based on location and semantic features.

Local Semi%2Dlinear Regression for River Runoff Forecasting.

A relation extraction method of Chinese named entities based on location and semantic features.

Ubiquitous personalized information processing with wildcards.

Active Learning with Adaptive Heterogeneous Ensembles.
Abstract—One common approach to active learning is to iteratively train a single classifier by choosing data points based on its uncertainty, but it is nontrivial to design uncertainty measures unbiased by the choice of classifier. Query by committee [1] suggests that given an ensemble of diverse but accurate classifiers, the most informative data points are those that cause maximal disagreement among the predictions of the ensemble members. However the method for finding ensembles appropriate to a given data set remains an open question. In this paper, the random subspace method is combined with active learning to create multiple instances of different classifier types, and an algorithm is introduced that adapts the ratio of different classifier types in the ensemble towards better overall accuracy. Here we show that the proposed algorithm outperforms C4.5 with uncertainty sampling, Naive Bayes with uncertainty sampling, bagging, boosting and the random subspace method with random sampling. To the best of our knowledge, our work is the first to adapt the ratio of classifiers in a heterogeneous ensemble for active learning.
Vague One%2DClass Learning for Data Streams.

Multi%2Dsphere Support Vector Data Description for Outliers Detection on Multi%2Ddistribution Data.

Approximate Repeating Pattern Mining with Gap Requirements.

Error Detection and Uncertainty Modeling for Imprecise Data.

Clustering Web Services for Automatic Categorization.

Pattern Matching with Wildcards based on Key Character Location.

An Aggregate Ensemble for Mining Concept Drifting Data Streams with Noise.

Parameter Estimdation in Semi%2DRandom Decision Tree Ensembling on Streaming Data.

A Comparative Study of Pattern Matching Algorithms on Sequences.

BPBM An Algorithm for String Matching with Wildcards and Length Constraints.

Mining globally interesting patterns from multiple databases using kernel estimation.

An Agent%2DBased Hybrid System for Microarray Data Analysis.

Optimizing Service Systems Based on Application%2DLevel QoS.

Optimizing Service Systems Based on Application%2DLevel QoS.



Geometric Mean for Subspace Selection.

Ubiquitous Mining with Interactive Data Mining Agents.

Regional category parsing in undirected graphical models.

Mining Concept%2DDrifting Data Streams with Multiple Semi%2DRandom Decision Trees.

An Intrusion Detection Model Based on Mining Data Streams.

A New Descriptive Clustering Algorithm based on Nonnegative Matrix Factorization.

Data Mining Algorithms and Problems.
Business process automation technologies are  being increasingly used by many companies to  improve the efficiency of both internal processes  as well as of e-services offered to customers. In  order to satisfy customers and employees,  business processes need to be executed with a  high and predictable quality. In particular, it is  crucial for organizations to meet the Service  Level Agreements (SLAs) stipulated with the  customers and to foresee as early as possible the  risk of missing SLAs, in order to set the right  expectations and to allow for corrective actions.  In this paper we focus on a critical issue in  business process quality: that of analyzing,  predicting and preventing the occurrence of  exceptions, i.e., of deviations from the desired or  acceptable behavior. We characterize the  problem and propose a solution, based on data  warehousing and mining techniques. We then  describe the architecture and implementation of a  tool suite that enables exception analysis,  prediction, and prevention. Finally, we show  experimental results obtained by using the tool  suite to analyze internal HP processes.  1. 
Cleansing Noisy Data Streams.

Multilayer Change%2DPoint Detection on Stock Order Flows by Wavelet Transformation.

Keyword Extraction Based on Lexical Chains and Word Co%2Doccurrence for Chinese News Web Pages.

Gene expression analyses using Genetic Algorithm based hybrid approaches.

Bayesian tensor analysis.

Keyphrase Extraction from Chinese News Web Pages Based on Semantic Relations.

Keyphrase Extraction from Chinese News Web Pages Based on Semantic Relations.

Automatic Recognition of News Web Pages.

Error%2DTolerant Data Mining.

Data Mining.

Conceptual equivalence for contrast mining in classification learning.
Learning often occurs through comparing. In classification learning, in order to compare data groups, most existing methods compare either raw instances or learned classification rules against each other. This paper takes a different approach, namely conceptual equivalence, that is, groups are equivalent if their underlying concepts are equivalent while their instance spaces do not necessarily overlap and their rule sets do not necessarily present the same appearance. A new methodology of comparing is proposed that learns a representation of each group’s underlying concept and respectively crossexams one group’s instances by the other group’s concept representation. The innovation is five-fold. First, it is able to quantify the degree of conceptual equivalence between two groups. Second, it is able to retrace the source of discrepancy at two levels: an abstract level of underlying concepts and a specific level of instances. Third, it applies to numeric data as well as categorical data. Fourth, it circumvents direct comparisons between (possibly alarge number of) rules that demand substantial effort. Fifth, it reduces dependency on the accuracy of employed classification algorithms. Empirical evidence suggests that this new methodology is effective and yet simple to use in scenarios such as noise cleansing and concept-change learning.
Bayesian Tensor Approach for 3%2DD Face Modeling.

TKDE 20%2812%29 %28December 2008%29 EIC Editorial State of the Transactions.

Editorial TKDE Editorial Board Changes.

Mining With Noise Knowledge Error%2DAware Data Mining.

Top 10 algorithms in data mining.
Abstract This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community. With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and review current and further research on the algorithm. These 10 algorithms cover classification,


Tensor Rank One Discriminant Analysis %2D A convergent method for discriminative multilinear subspace selection.

Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
We present a family of algorithms to uncover tribes—groups of individuals who share unusual sequences of affiliations. While much work inferring community structure describes large-scale trends, we instead search for small groups of tightly linked individuals who behave anomalously with respect to those trends. We apply the algorithms to a large temporal and relational data set consisting of millions of employment records from the National Association of Securities Dealers. The resulting tribes contain individuals at higher risk for fraud, are homogenous with respect to risk scores, and are geographically mobile, all at significant levels compared to random or to other sets of individuals who share affiliations.

Measuring the Uncertainty of Differences for Contrasting Groups.


SAIL%2DAPPROX An Efficient On%2DLine Algorithm for Approximate Pattern Matching with Wildcards and Length Constraints.

Mining with Noise Knowledge Error Aware Data Mining.

Mining Frequent Itemsets Using a Pruned Concept Lattice.

Discovering Relational Patterns across Multiple Databases.

Probabilistic Tensor Analysis with Akaike and Bayesian Information Criteria.

General Averaged Divergence Analysis.

Noise Modeling with Associative Corruption Rules.

Probabilistic Tensor Analysis with Akaike and Bayesian Information Criteria.

An Empirical Study of the Noise Impact on Cost%2DSensitive Learning.

Mining Complex Patterns across Sequences with Gap Requirements.

Mining Frequent Patterns with Wildcards from Biological Sequences.

Varying Density Spatial Clustering Based on a Hierarchical Tree.

A Parallel Algorithm for Learning Bayesian Networks.

Class Noise vs Attribute Noise Their Impacts%2C Detection and Cleansing.

A New Algorithm for Attribute Reduction in Decision Tables.

EIC Editorial 2007 TKDE Editorial Board Changes.

TKDE Guidelines for Survey Papers.

General Tensor Discriminant Analysis and Gabor Features for Gait Recognition.

Real%2DTime Texture Synthesis Using s%2DTile Set.

A Semi%2DRandom Multiple Decision%2DTree Algorithm for Mining Data Streams.

Mining maximal frequent itemsets from data streams.

Supervised tensor learning.
This paper aims to take general tensors as inputs for supervised learning. A supervised tensor learning (STL) framework is established for convex optimization based learning techniques such as support vector machines (SVM) and minimax probability machines (MPM). Within the STL framework, many conventional learning machines can be generalized to take n th –order tensors as inputs. We also study the applications of tensors to learning machine design and feature extraction by linear discriminant analysis (LDA). Our method for tensor based feature extraction is named the tenor rank–one discriminant analysis (TR1DA). These generalized algorithms have several advantages: 1) reduce the curse of dimension problem in machine learning and data mining; 2) avoid the failure to converge; and 3) achieve better separation between the different categories of samples. As an example, we generalize MPM to its STL version, which is named the tensor MPM (TMPM). TMPM learns a series of tensor projections iteratively. It is then evaluated against the original MPM. Our experiments on a binary classification problem show that TMPM significantly outperforms the original MPM. 1.
Mining Sequential Patterns across Time Sequences.

Generic object recognition with regional statistical models and layer joint boosting.

Human Carrying Status in Visual Surveillance.
A person’s gait changes when he or she is carrying an object such as a bag, suitcase or rucksack. As a result, human identification and tracking are made more difficult because the averaged gait image is too simple to represent the carrying status. Therefore, in this paper we first introduce a set of Gabor based human gait appearance models, because Gabor functions are similar to the receptive field profiles in the mammalian cortical simple cells. The very high dimensionality of the feature space makes training difficult. In order to solve this problem we propose a general tensor discriminant analysis (GTDA), which seamlessly incorporates the object (Gabor based human gait appearance model) structure information as a natural constraint. GTDA differs from the previous tensor based discriminant analysis methods in that the training converges. Existing methods fail to converge in the training stage. This makes them unsuitable for practical tasks. Experiments are carried out on the USF baseline data set to recognize a human’s ID from the gait silhouette. The proposed Gabor gait incorporated with GTDA is demonstrated to significantly outperform the existing appearance-based methods. 1.
User%2DCentered Agents for Structured Information Location on the Web.

Error awareness data mining.

Corrective Classification Classifier Ensembling with Corrective and Diverse Base Learners.

Scalable Representative Instance Selection and Ranking.

Ontology%2Dbased feature weighting for biomedical literature classification.

Triangulation of Bayesian Networks Using an Adaptive Genetic Algorithm.

Identifying bridging rules between conceptual clusters.

SVM%2DOD SVM Method to Detect Outliers.



Mining in Anticipation for Concept Change Proactive%2DReactive Prediction in Data Streams.
Abstract. Prediction in streaming data is an important activity in the modern society. Two major challenges posed by data streams are (1) the data may grow without limit so that it is difficult to retain a long history of raw data; and (2) the underlying concept of the data may change over time. The novelties of this paper are in four folds. First, it uses a measure of conceptual equivalence to organize the data history into a history of concepts. This contrasts to the common practice that only keeps recent raw data. The concept history is compact while still retains essential information for learning. Second, it learns concept-transition patterns from the concept history and anticipates what the concept will be in the case of a concept change. It then proactively prepares a prediction model for the future change. This contrasts to the conventional methodology that passively waits until the change happens. Third, it incorporates proactive and reactive predictions. If the anticipation turns out to be correct, a proper prediction model can be launched instantly
EIC Editorial TKDE Editorial Board Changes.

A logical framework for identifying quality knowledge from different data sources.

EIC Editorial State of the Transactions.

Class Noise Handling for Effective Cost%2DSensitive Learning by Cost%2DGuided Iterative Classification Filtering.

EIC Editorial TKDE Editorial Board Changes.

Asymmetric Bagging and Random Subspace for Support Vector Machines%2DBased Relevance Feedback in Image Retrieval.

10 Challenging Problems in Data Mining Research.
Statistical machine learning techniques for data classification usually assume that all entities are i.i.d. (independent and identically distributed). However, real-world entities often interconnect with each other through explicit or implicit relationships to form a complex network. Although some graph-based classification methods have emerged in recent years, they are not really suitable for complex networks as they do not take the degree distribution of network into consideration. In this paper, we propose a new technique, Modularity Kernel, that can effectively exploit the latent community structure of networked entities for their classification. A number of experiments on hypertext datasets show that our proposed approach leads to excellent classification performance in comparison with the state-of-the-art methods.
Efficient string matching with wildcards and length constraints.

Supervised Tensor Learning.
This paper aims to take general tensors as inputs for supervised learning. A supervised tensor learning (STL) framework is established for convex optimization based learning techniques such as support vector machines (SVM) and minimax probability machines (MPM). Within the STL framework, many conventional learning machines can be generalized to take n th –order tensors as inputs. We also study the applications of tensors to learning machine design and feature extraction by linear discriminant analysis (LDA). Our method for tensor based feature extraction is named the tenor rank–one discriminant analysis (TR1DA). These generalized algorithms have several advantages: 1) reduce the curse of dimension problem in machine learning and data mining; 2) avoid the failure to converge; and 3) achieve better separation between the different categories of samples. As an example, we generalize MPM to its STL version, which is named the tensor MPM (TMPM). TMPM learns a series of tensor projections iteratively. It is then evaluated against the original MPM. Our experiments on a binary classification problem show that TMPM significantly outperforms the original MPM. 1.
Effective classification of noisy data streams with attribute%2Doriented dynamic classifier selection.
Abstract. Recently, mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a new dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single ”best ” classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence.
A Decremental Algorithm for Maintaining Frequent Itemsets in Dynamic Databases.
Abstract. Data mining and machine learning must confront the problem of pattern maintenance because data updating is a fundamental operation in data management. Most existing data-mining algorithms assume that the database is static, and a database update requires rediscovering all the patterns by scanning the entire old and new data. While there are many efficient mining techniques for data additions to databases, in this paper, we propose a decremental algorithm for pattern discovery when data is being deleted from databases. We conduct extensive experiments for evaluating this approach, and illustrate that the proposed algorithm can well model and capture useful interactions within data when the data is decreasing. 1
Supervised Tensor Learning.
This paper aims to take general tensors as inputs for supervised learning. A supervised tensor learning (STL) framework is established for convex optimization based learning techniques such as support vector machines (SVM) and minimax probability machines (MPM). Within the STL framework, many conventional learning machines can be generalized to take n th –order tensors as inputs. We also study the applications of tensors to learning machine design and feature extraction by linear discriminant analysis (LDA). Our method for tensor based feature extraction is named the tenor rank–one discriminant analysis (TR1DA). These generalized algorithms have several advantages: 1) reduce the curse of dimension problem in machine learning and data mining; 2) avoid the failure to converge; and 3) achieve better separation between the different categories of samples. As an example, we generalize MPM to its STL version, which is named the tensor MPM (TMPM). TMPM learns a series of tensor projections iteratively. It is then evaluated against the original MPM. Our experiments on a binary classification problem show that TMPM significantly outperforms the original MPM. 1.
ACE An Aggressive Classifier Ensemble with Error Detection

Scalable Inductive Learning on Partitioned Data.

Combining proactive and reactive predictions for data streams.
Mining data streams is important in both science and commerce. Two major challenges are (1) the data may grow without limit so that it is difficult to retain a long history; and (2) the underlying concept of the data may change over time. Different from common practice that keeps recent raw data, this paper uses a measure of conceptual equivalence to organize the data history into a history of concepts. Along the journey of concept change, it identifies new concepts as well as re-appearing ones, and learns transition patterns among concepts to help prediction. Different from conventional methodology that passively waits until the concept changes, this paper incorporates proactive and reactive predictions. In a proactive mode, it anticipates what the new concept will be if a future concept change takes place, and prepares prediction strategies in advance. If the anticipation turns out to be correct, a proper prediction model can be launched instantly upon the concept change. If not, it promptly resorts to a reactive mode: adapting a prediction model to the new data. A system RePro is proposed to implement these new ideas. Experiments compare the system with representative existing prediction methods on various benchmark data sets that represent diversified scenarios of concept change. Empirical evidence demonstrates that the proposed methodology is an effective and efficient solution to prediction for data streams.
Rearranging data objects for efficient and stable clustering.

Discretization Methods.
Many machine learning and neurally inspired algorithms are limited, at least in their pure form, to working with nominal data. However, for many real-world problems, some provision must be made to support processing of continuously valued data. This paper presents empirical results obtained by using six different discretization methods as preprocessors to three different supervised learners on several real-world problems. No discretization technique clearly outperforms the others. Also, discretization as a preprocessing step is in many cases found to be inferior to direct handling of continuously valued data. These results suggest that machine learning algorithms should be designed to directly handle continuously valued data rather than relying on preprocessing or ad hoc techniques. 1.
EIC Editorial TKDE Editorial Board Changes.

Video Data Mining Semantic Indexing and Event Detection from the Association Perspective %2D Appendices.

Video Data Mining Semantic Indexing and Event Detection from the Association Perspective.
Abstract—Advances in the media and entertainment industries, including streaming audio and digital TV, present new challenges for managing and accessing large audio-visual collections. Current content management systems support retrieval using low-level features, such as motion, color, and texture. However, low-level features often have little meaning for naive users, who much prefer to identify content using high-level semantics or concepts. This creates a gap between systems and their users that must be bridged for these systems to be used effectively. To this end, in this paper, we first present a knowledge-based video indexing and content management framework for domain specific videos (using basketball video as an example). We will provide a solution to explore video knowledge by mining associations from video data. The explicit definitions and evaluation measures (e.g., temporal support and confidence) for video associations are proposed by integrating the inherent feature of video data. Our approach uses video processing techniques to find visual and audio cues (e.g., court field, camera motion activities, and applause), introduces multilevel sequential association mining to explore associations among the audio and visual cues, classifies the associations by assigning each of them with a class label, and uses their appearances in the video to construct video indices. Our experimental results demonstrate the performance of the proposed approach. Index Terms—Video mining, multimedia systems, database management, knowledge-based systems. æ 1
Support vector machines based on K%2Dmeans clustering for real%2Dtime business intelligence systems.

Editorial TKDE Topic Area Revisions.

Support vector machines based on K%2Dmeans clustering for real%2Dtime business intelligence systems.

Database classification for multi%2Ddatabase mining.

Mining Frequent Patterns with the Pattern Tree.

Error Detection and Impact%2DSensitive Instance Ranking in Noisy Datasets.
Given a noisy dataset, how to locate erroneous instances and attributes and rank suspicious instances based on their impacts on the system performance is an interesting and important research issue. We provide in this paper an Error Detection and Impact-sensitive instance Ranking (EDIR) mechanism to address this problem. Given a noisy dataset D, we first train a benchmark classifier T from D. The instances, that cannot be effectively classified by T are treated as suspicious and forwarded to a subset S. For each attribute A i, we switch A i and the class label C to train a classifier AP i for A i. Given an instance I k in S, we use AP i and the benchmark classifier T to locate the erroneous value of each attribute A i. To quantitatively rank instances in S, we define an impact measure based on the Information-gain Ratio (IR). We calculate IR i between attribute A i and C, and use IR i as the impact-sensitive weight of A i. The sum of impact-sensitive weights from all located erroneous attributes of I k indicates its total impact value. The experimental results demonstrate the effectiveness of our strategies. 1.
An Intelligent Digital Library System for Biologists.
To aid researchers in obtaining, organizing and managing biological data, we have developed a sophisticated digital library system that utilizes advanced data mining techniques [Stone et al 2004a]. Our digital library system is implemented as a centralized J2EE web application with links to publicly accessible data repositories on the Internet. The digital library is based on a framework used for conventional libraries and an objectoriented paradigm, and provides personalized user-centered services based on the user’s areas of interests and preferences. To make personalized service possible, a “user profile” that represents the preferences of an individual user is constructed based upon a user’s past activities, goals indicated by the user, and options. Utilizing these user profiles, our system makes relevant information available to the user in an appropriate form, amount, and level of detail with minimal user effort. The core of our project is an agent architecture that provides advanced services by combining data mining capabilities with domain knowledge in the form of a semantic network [Stone et al 2004b]. The semantic network imparts a knowledge structure through which the system can “reason ” and draw conclusions about biological data objects and provides a federated view of the many disparate databases of interest to biologists. In the development of our semantic network, we have included the concepts from several established controlled vocabularies, chief
Data Mining Artificial Intelligence in Data Analysis.

Cost%2DGuided Class Noise Handling for Effective Cost%2DSensitive Learning.
Recent research in machine learning, data mining and related areas has produced a wide variety of algorithms for costsensitive (CS) classification, where instead of maximizing the classification accuracy, minimizing the misclassification cost becomes the objective. However, these methods assume that training sets do not contain significant noise, which is rarely the case in real-world environments. In this paper, we systematically study the impacts of class noise on CS learning, and propose a cost-guided class noise handling algorithm to identify noise for effective CS learning. We call it Cost-guided Iterative Classification Filter (CICF), because it seamlessly integrates costs and an existing Classification Filter [1] for noise identification. Instead of putting equal weights to handle noise in all classes in existing efforts, CICF puts more emphasis on expensive classes, which makes it especially successful in dealing with datasets with a large cost-ratio. Experimental results and comparative studies from real-world datasets indicate that the existence of noise may seriously corrupt the performance of CS classifiers, and by adopting the proposed CICF algorithm, we can significantly reduce the misclassification cost of a CS classifier in noisy environments. 1.
Dynamic Classifier Selection for Effective Mining from Noisy Data Streams.
Recently, mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a new dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single “best” classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence. 1.
Data Acquisition with Active and Impact%2DSensitive Instance Selection.

OIDM Online Interactive Data Mining.

Dealing with Predictive%2Dbut%2DUnpredictable Attributes in Noisy Data Sources.
Abstract. Attribute noise can affect classification learning. Previous work in handling attribute noise has focused on those predictable attributes that can be predicted by the class and other attributes. However, attributes can often be predictive but unpredictable. Being predictive, they are essential to classification learning and it is important to handle their noise. Being unpredictable, they require strategies different from those of predictable attributes. This paper presents a study on identifying, cleansing and measuring noise for predictive-but-unpredictable attributes. New strategies are accordingly proposed. Both theoretical analysis and empirical evidence suggest that these strategies are more effective and more efficient than previous alternatives. 1
Data Mining Artificial Intelligence in Data Analysis.

Efficient mining of both positive and negative association rules.

Class Noise vs. Attribute Noise A Quantitative Study.

Data Mining An AI Perspective.

Parameter Tuning for Induction%2DAlgorithm%2DOriented Feature Elimination.

Guest Editors%27 Introduction Mining Actionable Knowledge on the Web.

Editorial Introducing the New Editor%2Din%2DChief.

Exploring video content structure for hierarchical summarization.

Eliminating Class Noise in Large Datasets.
This paper presents a new approach for identifying and eliminating mislabeled instances in large or distributed datasets. We first partition a dataset into subsets, each of which is small enough to be processed by an induction algorithm at one time. We construct good rules from each subset, and use the good rules to evaluate the whole dataset. For a given instance Ik, two error count variables are used to count the number of times it has been identified as noise by all subsets. The instance with higher error values will have a higher probability of being a mislabeled example. Two threshold schemes, majority and non-objection, are used to identify the noise. Experimental results and comparative studies from real-world datasets are reported to evaluate the effectiveness and efficiency of the proposed approach. 1.
Mining Video Associations for Efficient Database Management.
To support more efficient video database management, this paper explores the concept of video association mining, with which the association patterns are characterized by sequentially associated video shots and their cluster information. Given a continuous video sequence V, the video shot segmentation mechanism is first introduced to parse it into discrete shots. We then cluster shots into visually distinct groups and construct a shot cluster sequence by using the class label of each shot. An association mining scheme is designed to mine sequentially associated clusters from the sequence. Those detected associations will convey valuable knowledge for video database management. The experimental results demonstrate the effectiveness of our design. 1
Multi%2DDatabase Mining.
Multi-database mining is an important research area  because (1) there is an urgent need for analyzing data in different sources, (2) there are essential differences between mono- and multi-database mining, and (3) there are limitations in existing multi-database mining efforts. This paper designs a new multidatabase mining process. Some research issues involving mining multi-databases, including database clustering and local pattern analysis, are discussed.
Synthesizing High%2DFrequency Rules from Different Data Sources.

Online First publication.
reproduced or transmitted, in any form or by any means, without permission.
Data Mining How Research Meets Practical Development%3F
At the 2001 IEEE International Conference on Data Mining in San Jose, California on  November 29 - December 2, 2001, there was a panel discussion on how data mining research  meets practical development. One of the motivations for organizing the panel discussion was to  provide useful advice for industrial people to explore their directions in data mining development.
Hierarchical video content description and summarization using unified semantic and visual similarity.
Vide is increasingly the medium of choice for a variety of communication channeca renneca primarily from incre8kw le vex ofneh orke multimeST systeme One way to keW ourheSw above the vide se is to provide summarie in a more tractable format. Manye xistingapproache are limite to e xploring important low-le ve lfe9hxL re9hxL units for summarization. Unfortunatew ,the sew8WSTPk conteW andstructure of the vide do not corre9STP to low-le ve lfeNNwwS direwwS ,e ve n with close99STPLxPkS sceS deSe9STP and audio signal proceo -S8k The drawbacks ofe xisting meting are the following: (1) insteL of unfolding seolding and structure withinthe videi low-le ve l units usually addrey onlythe deS8h8 and (2) any important unitsetShhxN strate gybase on low-le ve lfe9 ture cannotbe applie togehWW8 videW8 Providingusen with an ove99w w ofthe vide contex at variousle ve8 of summarization is eSkL8WST formore e ficieP database reaba val and browsing. In thispape , we preWPW ahiexWST89xk vide conteW deteWST89 and summarizationstrate gysupporte by a nove l joint sentS9P and visual similaritystrate gy. TodeP9WkS the vide conteW e ficieWkS and accurateT , avide conteP de scription ontology isadopteL Variousvide procehxLw teoc nique are the utilize to construct asewx9ST8hPkwS vide annotationframe work. Byinte grating acquire contee de scription data, a hieNLSThxhW vide conteL structure is constructe with groupme ging and clusteWSTh Finally, a four laye vide summary with diffeSh9 granularitie isasseWPkS to assistuses in unfoldingthe vide contei in aprogreS sive way.ExpeSThW9w onrehWL ordvidek have validate the effectiveness of the proposed approach.
Association Analysis with One Scan of Databases.
Mining frequent patterns with an FP-tree avoids costly candidate generation and repeatedly occurrence frequency checking against the support threshold. It therefore achieves better performance and efficiency than Apriorilike algorithms. However, the database still needs to be scanned twice to get the FP-tree. This can be very time-consuming when new data are added to an existing database because two scans may be needed for not only the new data but also the existing data. This paper presents a new data structure P-tree, Pattern Tree, and a new technique, which can get the P-tree through only one scan of the database and can obtain the corresponding FP-tree with a specified support threshold. Updating a P-tree with new data needs one scan of the new data only, and the existing data do not need to be re-scanned. 1
Mining Both Positive and Negative Association Rules.
In this paper, we describe a novel technique, called APACS2, for mining interesting quantitative association rules from very large databases. To effectively mine such rules, APACS2 employs adjusted difference analysis. The use of this technique has the advantage that it does not require any user-supplied thresholds which are often hard to determine. Furthermore, APACS2 also has the advantage that it allows users to discover both positive and negative association rules. A positive association rule tells us that a record having certain attribute value will also have another attribute value whereas a negative association rule tells us that a record having certain attribute value will not have another attribute value. The fact that APACS2 is able to mine both positive and negative association rules and that it uses an objective yet meaningful measure to determine the interestingness of a rule makes it very effective at different data mining tasks.
Dynamic Refinement of Classification Rules.

Knowledge discovery in very large databases.
Although so-called &#034;naive&#034; Bayesian classification makes the unrealistic assumption that the values of the attributes of an example are independent given the class of the example, this learning method is remarkably successful in practice, and no uniformly better learning method is known. Boosting is a general method of combining multiple classifiers due to Yoav Freund and Rob Schapire. This paper shows that boosting applied to naive Bayesian classifiers yields combination classifiers that are representationally equivalent to standard feedforward multilayer perceptrons. (An ancillary result is that naive Bayesian classification is a nonparametric, nonlinear generalization of logistic regression.) As a training algorithm, boosted naive Bayesian learning is quite different from backpropagation, and has definite advantages. Boosting requires only linear time and constant space, and hidden nodes are learned incrementally, starting with the most important. On the realworld datasets on which the method has been tried so far, generalization performance is as good as or better than the best published result using any other learning method. Unlike all other standard learning algorithms, naive Bayesian learning, with and without boosting, can be done in logarithmic time with a linear number of parallel computing units. Accordingly, these learning methods are highly plausible computationally as models of animal learning. Other arguments suggest that they are plausible behaviorally also.
Message from the TCCI Chair.
The web log data embed much of web users&#039; browsing behavior. From the web logs, one can discover patterns that predict the users&#039; future requests based on their current behavior. These web data are very complex due to their large size and sequential nature. In the past, researchers have proposed different methods to predict what pages will be visited next based on their present visit patterns. In this paper, we extend this work to discover patterns that can predict when these web page accesses will occur. Our method is based on a novel extension of association rule classification method. We extend the traditional association rules by including the temporal information explicitly in each rule, and reason about the confidence of each prediction in terms of its temporal region. We compare two different methods for temporal event prediction, demonstrate the effectiveness of our methods empirically on realistic web logs, and explore the tradeoff between prediction accuracy and data mining time for our models.
Using Knowledge Anchors to Reduce Cognitive Overheads.

Proceedings of the 2001 IEEE International Conference on Data Mining
Text clustering typically involves clustering in a high dimensional space, which appears difficult with regard to virtually all practical settings. In addition, given a particular
Efficient Runtime Generation of Association Rules.

User%2DCentered Agents for Structured Information Location.

Large Scale Data Mining Based on Data Partitioning.

Building Intelligent Learning Database Systems.
Induction and deduction are two opposite operations in data mining applications. Induction  extracts knowledge in the form of, say, rules or decision trees from existing data, and deduction  applies induction results to interpret new data. An intelligent learning database (ILDB) system  integrates machine learning techniques with database and knowledge base technology. It starts  with existing database technology and performs both induction and deduction. The integration  of database technology, induction (from machine learning), and deduction (from knowledgebased  systems) plays a key role in the construction of ILDB systems, as does the design of  efficient induction and deduction algorithms. This paper presents a system structure for ILDB  systems, and discusses practical issues for ILDB applications, such as instance selection and  structured induction.  1 Introduction  Over the past thirty years database research has evolved technologies that are now widely used in almost every co...
Building Intelligent Learning Database Systems.
Induction and deduction are two opposite operations in data mining applications. Induction  extracts knowledge in the form of, say, rules or decision trees from existing data, and deduction  applies induction results to interpret new data. An intelligent learning database (ILDB) system  integrates machine learning techniques with database and knowledge base technology. It starts  with existing database technology and performs both induction and deduction. The integration  of database technology, induction (from machine learning), and deduction (from knowledgebased  systems) plays a key role in the construction of ILDB systems, as does the design of  efficient induction and deduction algorithms. This paper presents a system structure for ILDB  systems, and discusses practical issues for ILDB applications, such as instance selection and  structured induction.  1 Introduction  Over the past thirty years database research has evolved technologies that are now widely used in almost every co...
Knowledge object modeling.
classes define a general frame that their specializations must follow, they include &#034;holes&#034; in their definition that will be filled by their specializations. The different ways these specializations &#034;fill the same holes&#034; usually made them incompatible. But this rule has never been stated, we want a precise and explicit representation of the opposition.  One of the question we have not yet answered is whether the object model supports other types of opposition. In WindowTools (see previous section), all oppositions are based on this notion of abstract &#034;LOOM&#039;s partition&#034; classes, for example, MainWindow and SubWindow are sub-classes of XWindow the abstract class for general windows. Although it is not likely that other kind of opposition exist, it is not clear to us by now whether two non-siblings objects could be opposed or not.  4 Opposition relation utility  In this section, we study the particular contexts that could make use of the explicit representation of the opposition relation....
Induction as Pre%2Dprocessing.

Induction By Attribute Elimination.

Editorial.
calls &amp; calendarEDITORIAL
Editorial.
calls &amp; calendarEDITORIAL
Research and Development in Knowledge Discovery and Data Mining

Multi%2Dlayer Incremental Induction.
. This paper describes a multi-layer incremental induction algorithm, MLII, which is linked to an existing nonincremental induction algorithm to learn incrementally from noisy data. MLII makes use of three operations: data partitioning, generalization and reduction. Generalization can either learn a set of rules from a (sub)set of examples, or refine a previous set of rules. The latter is achieved through a redescription operation called reduction: from a set of examples and a set of rules, we derive a new set of examples describing the behaviour of the rule set. New rules are extracted from these behavioral examples, and these rules can be seen as meta-rules, as they control previous rules in order to improve their predictive accuracy. Experimental results show that MLII achieves significant improvement on the existing nonincremental algorithm HCV used for experiments in this paper, in terms of rule accuracy. 1 Introduction  Existing machine learning algorithms can be generally distin...
Interest Discovery for Incremental Web Exploration.

Object%2DOriented Modeling of Multimedia Documents.
Multimedia data has become readily available from a variety of resources, such as the Web, to users (ranging from naive to sophisticated) who need to select and to present the data in a way that is meaningful to their particular applications. Delaunay  MM  is our framework for querying and presenting multimedia data stored in distributed data repositories, including the Web. It is unique in combining user-defined layouts with ad hoc querying capabilities, thereby enabling users to tailor, in a simple way, the layout of virtual documents composed of retrieved multimedia objects. In this paper, we focus on the object-oriented data models, on the declarative query languages, and on how the results of the queries to disparate resources are integrated to form coherent user-defined documents. 1 Introduction  Database management systems (DBMSs) have traditionally enabled the storage, retrieval, and presentation of tabular datasets primarily for professional applications. The recent phenomenon...
Wide Area Selection as a Hyperdocument Search Interface.

Learning Design Knowledge as Generalization.

RIEVL Recursive Induction Learning in Hand Gesture Recognition.


LFA  A Fast Chaining Algorithm for Rule%2DBased Systems.


Schedular   Scheduling with Knowledge Objects.

A Study of Causal Discovery With Weak Links and Small Samples.
Weak causal relationships and small sample size pose two significant difficulties to the automatic discovery of causal models from observational data. This paper examines the influence of weak causal links and varying sample sizes on the discovery of causal models. The experimental results illustrate the effect of larger sample sizes for discovering causal models reliably and the relevance of the strength of causal links and the complexity of the original causal model. We present indicative evidence of the superior robustness of MML (Minimum Message Length) methods to standard significance tests in the recovery of causal links. The comparative results show that the MML-CI (the MML Causal Inducer) causal discovery system finds better models than TETRAD II given small samples from linear causal models. The experimental results also reveal that MML-CI finds weak links with smaller sample sizes than can TETRAD II.  
Hybrid Interpretation of %60No Match%27 and %60Multiple Match%27 in Induction.

SiteHelper A Localized Agent That Helps Incremental Exploration of the World Wide Web.

Disorientation and Cognitive Overhead in Hypertext Systems.
Disorientation and cognitive overhead are two interrelated problems that may in fact ultimately limit the usefulness of hypertext. Cognitive overhead upon the author arises from a viewpoint that sees the author as the person solely responsible for inserting all links within her work. This includes all links between the anchors in her own work and those in external frames, as well as cross-links between the anchors within her own work. The need for an author to be aware, for each anchor within her work, of all possible other anchors makes the insertion of such links an O(N  2  ) problem where N is the number of possible anchors in the hypertext universe. To reduce this to an O(N ) problem this paper proposes the use of bi-directional intelligent anchors. These are anchors that have both a knowledge of the concepts that a potential reader would be seeking were she to arrive at the anchor, together with a knowledge of the concepts that a reader would be seeking were she to jump from that ...
Rule Induction Without Decision Tree Construction.


RITIO %2D Rule Induction Two In One.

A Bayesian Discretizer for Real%2DValued Attributes.
Discretization of real-valued attributes into nominal intervals has been an important area for symbolic induction systems because many real world classification tasks involve both symbolic and numerical attributes. Among various supervised and unsupervised discretization methods, the information gain based methods have been widely used and cited. This paper designs a new discretization method, called the Bayesian discretizer, and compares its performance with some other methods including the information gain methods implemented in C4.5 and HCV (Version 2.0). Over the 7 tested datasets, the Bayesian discretizer has the best results for 3 in terms of predictive accuracy. 1 Introduction  In the context of rule induction and decision tree construction, dealing with a continuous attribute means discretization of the numerical attribute into a number of intervals. The discretized intervals can be treated in a similar way to nominal values during induction and deduction. The essential aspect ...

Fuzzy Interpretation of Induction Results.
When applying rules induced from training examples to a test example, there are three possible cases which demand different actions: (1) no match, (2) single match, and (3) multiple match.  Existing techniques for dealing with the first and third cases are exclusively based on probability estimation. However, when there are continuous attributes in the example space, and if these attributes have been discretised into intervals before induction, fuzzy interpretation of the discretised intervals at deduction time could be very valuable. This paper introduces the idea of using fuzzy borders for interpretation of discretised intervals at deduction time, and outlines the results we have obtained with the HCV (Version 2.0) software. Introduction  Knowledge discovery in databases (KDD) is a research frontier (Wu 93a) for both database technology and machine learning techniques, and has seen sustained research over recent years. It acts as a link between the two fields, thus offering a dual be...
Knowledge Objects.
ion and encapsulation  Abstraction is the principle of capturing useful information by ignoring all the detailed features of an entity that are not relevant to understanding what it does or what it is. Rather than trying  KNOWLEDGE OBJECTS Informatica 3 to comprehend everything about the entity all at once, we select only part of it. Abstraction consists of &#034;data abstraction&#034; and &#034;procedural abstraction&#034;. Procedural abstraction can already be found in most imperative programming languages in the form of functions and procedures, which can be used to reduce the complexity of programming code. In OOD, data abstraction is carried out by the definitions of abstract data types (ADTs) -- commonly called classes or  types [Atkinson et al. 92]. An ADT is defined in terms of data items and the operations, called  methods in OOP, that can be applied to these data items. The data within the ADT can only be modified and manipulated by these methods. The resulting notion of encapsulation leads to ...
Lecture Notes in Machine Learning.

The HCV Induction Algorithm.
This paper presents a heuristic, attribute-based, noise-tolerant data mining program, HCV (Version 2.0), based on the newly-developed extension matrix approach. By dividing the positive examples (PE) of a specific class in a given example set into intersecting groups and adopting a set of strategies to find a heuristic conjunctive formula in each group which covers all the group&#039;s positive examples and none of the negative examples (NE), the HCV induction algorithm adopted in the HCV (Version 2.0) software finds a description formula in the form of variable-valued logic for PE against NE in low-order polynomial time at induction time. In addition to the HCV induction algorithm, this paper also outlines some of the techniques for noise handling and discretization of numerical domains developed and implemented in the HCV (Version 2.0) software, and provides a performance comparison of HCV (Version 2.0) with other data mining algorithms ID3, C4.5, C4.5rules and NewID in noisy and continuo...
Inductive learning Algorithms and frontiers.

A Prolog%2DBased Presentation for Integrating Knowledge and Data.

